# 超时了
from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        return self.find(0, nums, S)

    def find(self, index, nums: List[int], sum: int) -> int:
        if index == len(nums):
            if sum == 0:
                return 1
            else:
                return 0
        return self.find(index + 1, nums, sum + nums[index]) + self.find(index + 1, nums, sum - nums[index])

solu = Solution()
print(solu.findTargetSumWays([1, 1, 1, 1, 1], 3))
print(solu.findTargetSumWays([1, 0], 1))